MOD = 10 ** 9 + 7


class Solution:
    def countOrders(self, n: int) -> int:
        if n == 1:
            return 1

        ans = 1
        for i in range(2, n + 1):
            # 之前的P和D共有：2*(i-1)个；空隙数=2*(i-1)+1
            # 新来包裹的P和D是挨着的，可以插入到之前任何一个空隙中
            ans1 = ans * (2 * (i - 1) + 1)

            # 信赖的包括的P和D是不挨着的，但是P必须在D前面：C(2,2*(i-1)+1)
            ans2 = ans * (2 * (i - 1) + 1) * (2 * (i - 1)) // 2

            ans = (ans1 + ans2) % MOD

        return ans


if __name__ == "__main__":
    print(Solution().countOrders(1))  # 1
    print(Solution().countOrders(2))  # 6
    print(Solution().countOrders(3))  # 90
